蓝桥杯2023年第十四届省赛 python B组 题解

C - 松散子序列

s = input()
n = len(s)
f = [[0, 0] for _ in range(n + 1)]
f[0][0] = 0
f[0][1] = ord(s[0]) - ord('a') + 1
for i in range(1, n):
    f[i][0] = max(f[i - 1][0], f[i - 1][1])
    f[i][1] = f[i - 1][0] + ord(s[i]) - ord('a') + 1

print(max(f[n - 1][0], f[n - 1][1]))

D - 管道

INF = 100000000000

n, m = map(int, input().split())

a = []

def check(T): # 询问在 T 时刻是否可以填满管道
    
    b = []
    for i in range(n):
        if a[i][1] <= T:
            b.append(a[i])

    if len(b) == 0:
        return 0

    now_n = len(b)
    pre = [0] * now_n
    lst = [0] * now_n

    for i in range(now_n):
        L, S = b[i]
        if i == 0:
            pre[i] = L + (T - S)
        else:
            pre[i] = max(pre[i - 1], L + (T - S))
    
    for i in range(now_n - 1, -1, -1):
        L, S = b[i]
        if i == now_n - 1:
            lst[i] = L - (T - S)
        else:
            lst[i] = min(lst[i + 1], L - (T - S))
    
    for i in range(1, now_n):
        if lst[i] - pre[i - 1] > 1:
            return 0
    if lst[0] > 1 or pre[now_n - 1] < m:
        return 0
    return 1

for i in range(n):
    L, S = map(int, input().split())
    a.append((L, S))

a.sort(key=lambda x : (x[0]))

L_, R_ = 0, INF

while L_ + 1 < R_:
    mid = (L_ + R_) // 2
    if check(mid):
        R_ = mid
    else:
        L_ = mid

print(R_)